package kyssion.leetcode.num1_50;

import kyssion.leetcode.util.ShowUtil;

/**
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 你的算法时间复杂度必须是 O(log n) 级别。
 * <p>
 * 如果数组中不存在目标值，返回 [-1, -1]。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例 2:
 * <p>
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 */
public class code34_在排序数组中查找元素的第一个和最后一个位置 {
    public static void main(String[] args) {
        ShowUtil.showArr(new code34_在排序数组中查找元素的第一个和最后一个位置().searchRange(
                new int[]{
                        0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 8, 10, 10
                }, 4
        ));
    }

    /**
     * 这题也没什么好说的正常思路
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        int[] iii = new int[]{
                -1, -1
        };
        if (nums.length == 0) {
            return iii;
        }
        int index = find(nums, 0, nums.length - 1, target);
        if (index == -1) {
            return iii;
        }
        int left = findleft(nums, 0, index - 1, target);
        int right = findright(nums, index + 1, nums.length - 1, target);
        iii[0] = left == -1 ? index : left;
        iii[1] = right == -1 ? index : right;
        return iii;
    }

    public int findright(int[] nums, int left, int right, int target) {
        int midle = 0;
        while (left <= right) {
            midle = (left + right) >> 1;
            if (nums[midle] != target) {
                return findright(nums, left, midle - 1, target);
            } else {
                int i = findright(nums, midle + 1, right, target);
                return i == -1 ? midle : i;
            }
        }
        return -1;
    }

    public int findleft(int[] nums, int left, int right, int target) {
        int midle = 0;
        while (left <= right) {
            midle = (left + right) >> 1;
            if (nums[midle] != target) {
                return findleft(nums, midle + 1, right, target);
            } else {
                int i = findleft(nums, left, midle - 1, target);
                return i == -1 ? midle : i;
            }
        }
        return -1;
    }

    public int find(int[] nums, int left, int right, int target) {
        int midle = 0;
        while (left <= right) {
            midle = (left + right) >> 1;
            if (nums[midle] == target) {
                return midle;
            } else if (nums[midle] > target) {
                right = midle - 1;
            } else {
                left = midle + 1;
            }
        }
        return -1;
    }

    /**
     * 记一个好一点的吧,通过不是查找1/2 位置而是缩进前端的位置来收敛 数字
     */
    public int[] searchRange2(int[] nums, int target) {
        int n = nums.length, i = 0, j = n - 1;
        int ans[] = new int[]{-1, -1};
        while (i <= j) {
            if (nums[i] == target) {
                ans[0] = i;
                break;
            }
            int mid = (i + j) / 2;
            if (target == nums[mid]) {
                j = mid;
            } else if (target > nums[mid]) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }

        if (ans[0] == -1) return ans;
        i = 0;
        j = n - 1;
        while (i <= j) {
            if (nums[j] == target) {
                ans[1] = j;
                break;
            }
            int mid = (i + j + 1) / 2;
            if (target == nums[mid]) {
                i = mid;
            } else if (target > nums[mid]) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return ans;

    }
}
